(1) Field of Invention
The present invention relates to a system tbr pattern matching and, more particularly, to a secure system for generic pattern matching.
(2) Description of Related Art
In computer science, pattern matching is the act of checking some sequence of characters from a fixed alphabet for the presence of the constituents of some pattern. The patterns generally have the form of a sequence of characters. Pattern matching has many applications in computer science including, but not limited to, text-processing, database operations, network filtering, and security applications. It is a problem that has been extensively researched, resulting in several efficient (although insecure) techniques to solve various variations thereof (see, for example, the List of Incorporated Literature References, Literature Reference Nos. 1, 11, and 18).
The prior state of the art includes the secure pattern matching protocols of Literature Reference Nos. 3-5, 9, and 19, none of which support the covert adversary model. Another Line of related work includes the more general secure computation protocols of Literature Reference No. 13, which are secure in the covert model but must rely on a Boolean circuit designed to perform pattern matching. The generic protocols of Literature Reference No. 13 have communication complexity proportional to the product of the text length and the pattern length, which is asymptotically larger than desired.
Although researched extensively, even in the insecure setting, there is not a single algorithm that performs well in all cases, is efficient in both its speed and memory usage, can handle wildcards, approximate matches and limited range queries (a single character wildcard allows a single digit range to be specified). Thus, a continuing need exists for a secure pattern matching method that is efficient in both its speed and memory usage, can handle wildcards, and approximate matches.